/*
 *https://leetcode.cn/problems/satisfiability-of-equality-equations/
 *990. 等式方程的可满足性
 *medium 吴朝泽 2024.9.27
 *并查集
 当遇到 "a==b" 时，将这两个变量合并到同一个集合中。这意味着根据等式，a 和 b 是相等的或属于同一类。
 在第二次遍历方程式时，当遇到 "a!=b" 时，需要检查 a 和 b 是否仍然被视为不同的变量。
 如果它们在同一个集合中（即 uf.find(a) == uf.find(b)），则说明根据之前的等式，它们是相等的，违反了当前的不等式条件。
*/

class union_find
{
    vector<int> parent;
    int group;
public:

    // 构造从 0 到 n - 1 的节点
    union_find(int n) :
        parent(n), group()
    {
        for (int i = 0; i < n; ++i)
        {
            parent[i] = i;
        }
        group = n;
    }

    // 合并两个节点
    void pair(int index1, int index2)
    {
        int root_1 = find(index1), root_2 = find(index2);
        if (root_1 != root_2)
        {
            --group;
        }
        parent[root_2] = root_1;
    }

    // 找到根节点
    int find(int index)
    {
        vector<int> temp;

        int root = index;
        for (; parent[root] != root; root = parent[root])
        {
            temp.emplace_back(root);
        }

        for (auto& it : temp)
        {
            parent[it] = root;
        }

        return root;
    }

    // 判断连接性
    bool check(int index1, int index2)
    {
        return find(index1) == find(index2);
    }

    // 返回连通图的数量
    int group_count()
    {
        return group;
    }
};

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        union_find uf(26);  

        for(string k : equations)
        {
            if(k[1] == '=')
            {
                int a = k[0] - 'a';
                int b = k[3] - 'a';
                uf.pair(a, b);
            }
        }
        for(string k : equations)
        {
            if(k[1] == '!')
            {
                int a = k[0] - 'a';
                int b = k[3] - 'a';
                if(uf.find(a) == uf.find(b))
                    return false;
            }
        }
        return true;
    }
};